#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ELEM_SIZE 500000

void bubble_sort(int *es, int size){
	int i,j,t ;
	int tag = 1;
	for( i = 0; i < size - 1 && tag; i++){
		tag = 0;
		for(j = 1; j < size - i; j++){
			if(es[j - 1] > es[j]){
				t = es[j-1];
				es[j-1] = es[j];
				es[j] = t;
				tag = 1;
			}
		}
	}
}
void insertion_sort(int *es, int size){
	int i, j, t;
	for ( i = 1; i < size; i++){
		t = es[i];
		for(j = i-1; j >=0; j--)
			if(t < es[j]) es[j+1] = es[j];
			else break;
		es[j+1] =  t;
	}
}
/* 双向冒泡排序 */
void cocktail_sort(int *es, int size){
	int i, t;
	int tag = 1,low = 0, high = size - 1;
	while(tag){
		tag = 0;
		for(i = low; i < high; i++)
			if(es[i] > es[i+1]){
				t = es[i];
				es[i] = es[i+1];
				es[i+1] = t;
				tag = 1;
			}
		high --;
		for(i = high; i > low; i--)
			if(es[i] < es[i-1]){
				t = es[i];
				es[i] = es[i-1];
				es[i-1] = t;
				tag = 1;
			}
		low ++;
	}
}

void counting_sort(int*es, int size){
	int *count;
	int max = es[0], min = es[0];
	int i, j, range, z;
	for(i = 1; i < size; i++){
		if(max < es[i]) max = es[i];
		if(min > es[i]) min = es[i];
	}
	range = max - min + 1;
	count = (int *) malloc(range * sizeof(int));
	if(!count) exit(-1);
	for(i = 0; i < range; i++)
		count[i] = 0;
	for(i = 0; i < size; i++)
		count[es[i] - min]++;

	
	z = 0;
	for(i = min; i < max + 1; i++)
		for(j = 0; j < count[i-min]; j++)
			es[z++] = i;
	free(count);
}
	
void merge(int *es, int low,int mid, int high){
	int a1 = low, a2 = mid+1;
	int *p1;
	int i = high - low + 1;
	p1 = (int *) malloc(i * sizeof(int));
	if(!p1)exit(255);
	i = 0;
	for(; a1 <= mid && a2 <=high;){
		if(es[a1] <= es[a2])
			p1[i++] = es[a1++];
		else p1[i++] = es[a2++];
	}
	for(; a1 <= mid;) p1[i++] = es[a1++];
	for(; a2 <= high;) p1[i++] = es[a2++];
	for(i = low; i <= high; i++)
		es[i] = p1[i-low];
	
	free(p1);
}
void merge_sort(int *es, int low, int high){
	int mid;
	if(high > low){
		mid = (low + high)/2;
		merge_sort(es,low,mid);
		merge_sort(es,mid+1,high);
		merge(es,low,mid,high);
	}
}

		
void quick_sort(int *es, int low, int high){
	int po = es[low];
	int i = low+1,j = high;
	int t;
	while(1){
		while(es[i] < po && i <= high) i++;
		while(es[j] > po) j--;
		if(i >= j) break;
		t = es[i]; 
		es[i] = es[j];
		es[j] = t;
	}
	es[low] = es[j];
	es[j] = po;
	if(j - low > 1)
		quick_sort(es, low, j-1);
	if(high - j > 1)
	quick_sort(es, j+1, high);
}

void adjust_heap(int *es, int i, int size){
	int lc = 2*i+1, rc = 2*i+2;
	int max = i;
	int t;
	if(lc < size && es[lc] > es[max])
		max = lc;
	if(rc < size && es[rc] > es[max])
		max = rc;
	if(max != i){
		t = es[i];
		es[i] = es[max];
		es[max] = t;
		adjust_heap(es, max, size);
	}
}

void heap_sort(int *es, int size){
	int i, j, t;
	for(i = (size-2)/2; i >=0; i--)
		adjust_heap(es, i, size);
	for(i = size - 1; i > 0; i--){
		t = es[0];
		es[0] = es[i];
		es[i] = t;
		adjust_heap(es,0,i);
	}
}

void show(int *es){
	int i;
	for(i = 0; i < ELEM_SIZE; i++){
		printf("%d\n",es[i]);
	}
}	


int main(){
	int elems[ELEM_SIZE];
	int i, j;

	srand(time(NULL));
	for (i = 0; i < ELEM_SIZE; i++)
		elems[i] = rand();
	//bubble_sort(elems, ELEM_SIZE);
	//insertion_sort(elems,ELEM_SIZE);
	//cocktail_sort(elems,ELEM_SIZE);
	//counting_sort(elems,ELEM_SIZE);
	merge_sort(elems,0,ELEM_SIZE - 1);
	//quick_sort(elems,0,ELEM_SIZE - 1);
	//printf("DD||\n");
	//heap_sort(elems, ELEM_SIZE );
	//show(elems);
}

